package cn.zifangsky.sort;

/**
 * 快速排序
 *
 * @author zifangsky
 * @date 2019/1/7
 * @since 1.0.0
 */
public class QuickSort {
    /**
     * 设置低于多少个数则采用插入排序
     */
    private static int CUT_OFF_NUM = 10;

    /**
     * 快速排序
     * <p><b>最坏时间复杂度：</b>O(NlogN)</p>
     * @author zifangsky
     * @date 2019/1/7 14:15
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static int[] sort(int[] array){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        return quickSort(array, 0, (array.length - 1));
    }

    /**
     * 快速排序
     * <p><b>最坏时间复杂度：</b>O(NlogN)</p>
     * @author zifangsky
     * @date 2019/1/7 14:15
     * @since 1.0.0
     * @param array 待排序数组
     * @param cutOffNum 指定低于多少个数就采用插入法排序
     */
    public static int[] sort(int[] array, int cutOffNum){
        if(array == null || array.length < 1 || cutOffNum < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        CUT_OFF_NUM = cutOffNum;
        return quickSort2(array, 0, (array.length - 1));
    }


    /**
     * 快速排序
     * @param array 待排序数组
     * @param startIndex 待排序数据段在数组中的开始索引
     * @param endIndex 待排序数据段在数组中的结束索引
     */
    private static int[] quickSort(int[] array, int startIndex, int endIndex){
        //1. 获取中位数
        int middle = getMedian(array, startIndex, endIndex);

        int i = startIndex, j = endIndex - 1;
        //2. 将小数字往前移动，大数字往后移动
        while (i >= 0 && j >= 0 && i <= j){
            while (i < endIndex && array[i] <= middle){
                i++;
            }
            while (j >= 0 && array[j] > middle){
                j--;
            }

            //3. 如果 i 还在 j 的左边，则将两个位置的数字交换位置，继续循环判断
            if(i <= j){
                swap(array, i, j);
                i++;
                j--;
            }
        }

        //3. 将中位数放在中间位置，也就是交换 i 和 中位数所在位置（endIndex - 1）的数字
        swap(array, i, endIndex);

        //3. 排列前半部分
        if(startIndex < i){
            quickSort(array, startIndex, (i - 1));
        }

        //4. 排列后半部分
        if(i < endIndex){
            quickSort(array, (i + 1), endIndex);
        }

        return array;
    }

    /**
     * 快速排序（改进版）
     * @param array 待排序数组
     * @param startIndex 待排序数据段在数组中的开始索引
     * @param endIndex 待排序数据段在数组中的结束索引
     */
    private static int[] quickSort2(int[] array, int startIndex, int endIndex){
        //低于某个长度，采用插入法排序
        if(startIndex + CUT_OFF_NUM >= endIndex){
            insertSort(array, startIndex, endIndex);
        }else {
            //1. 获取中位数
            int middle = getMedian(array, startIndex, endIndex);

            int i = startIndex, j = endIndex - 1;
            //2. 将小数字往前移动，大数字往后移动
            while (i < j){
                while (array[i] <= middle){
                    i++;
                }
                while (array[j] > middle){
                    j--;
                }

                //3. 如果 i 还在 j 的左边，则将两个位置的数字交换位置，继续循环判断
                if(i < j){
                    swap(array, i, j);
                    i++;
                    j--;
                }
            }

            //3. 将中位数放在中间位置，也就是交换 i 和 中位数所在位置（endIndex - 1）的数字
            swap(array, i, endIndex);

            //3. 排列前半部分
            if(startIndex < i){
                quickSort2(array, startIndex, (i - 1));
            }

            //4. 排列后半部分
            if(i < endIndex){
                quickSort2(array, (i + 1), endIndex);
            }
        }

        return array;
    }

    /**
     * 插入法排序
     * @param array 待排序数组
     * @param startIndex 待排序数据段在数组中的开始索引
     * @param endIndex 待排序数据段在数组中的结束索引
     */
    private static void insertSort(int[] array, int startIndex, int endIndex){
        for(int i = startIndex; i <= endIndex; i++){
            int temp = array[i];

            int j;
            for(j = (i - 1); j >= 0 && temp < array[j]; j--) {
                //如果temp < array[j]，则array[j]向右移动一位
                array[j + 1] = array[j];
            }
            //将temp放到正确位置
            array[j + 1] = temp;
        }
    }

    /**
     * 获取中位数
     * @param array 待排序数组
     * @param startIndex 待排序数据段在数组中的开始索引
     * @param endIndex 待排序数据段在数组中的结束索引
     */
    private static int getMedian(int[] array, int startIndex, int endIndex){
        int middle = (startIndex + endIndex) / 2;

        //1. middle处存放中位数
        if(array[middle] > array[endIndex]){
            swap(array, middle, endIndex);
        }
        if(array[startIndex] > array[endIndex]){
            swap(array, startIndex, endIndex);
        }
        if(array[startIndex] > array[middle]){
            swap(array, startIndex, middle);
        }

        //2.将中位数移到末尾
        swap(array, middle, endIndex);

        //3. 返回中位数
        return array[endIndex];
    }

    /**
     * 交换两个数
     */
    private static void swap(int[] array, int oneIndex, int otherIndex){
        int temp = array[oneIndex];
        array[oneIndex] = array[otherIndex];
        array[otherIndex] = temp;
    }

}
